<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Digital circuit sizing example (GP)</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/circuit_design/html/dig_ckt_sizing.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Digital circuit sizing example (GP)</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd, Kim, Patil, and Horowitz, "Digital circuit optimization</span>
<span class="comment">% via geometric programming"</span>
<span class="comment">% Written for CVX by Almir Mutapcic 02/08/06</span>
<span class="comment">%</span>
<span class="comment">% Solves the problem of choosing gate scale factors x_i to give</span>
<span class="comment">% minimum ckt delay, subject to limits on the total area and power.</span>
<span class="comment">% Uses max gate arrival time T formulation that avoids evaluation</span>
<span class="comment">% of the delay over all paths in the circuit.</span>
<span class="comment">%</span>
<span class="comment">%   minimize   T_bar</span>
<span class="comment">%       s.t.   T_j &lt;= T_bar      for j an output gate</span>
<span class="comment">%              T_j + d_i &lt;= T_i  for j in FI(i)</span>
<span class="comment">%              P &lt;= Pmax, A &lt;= Amax</span>
<span class="comment">%              x &gt;= 1</span>
<span class="comment">%</span>
<span class="comment">% where variables are x and T.</span>
<span class="comment">%</span>
<span class="comment">% We use the circuit topology presented in figure 1 (page 902),</span>
<span class="comment">% where we take gates 1, 3 and 6 to be inverters (INV),</span>
<span class="comment">% gates 2 and 7 to be three input NANDs (NAND3),</span>
<span class="comment">% and gates 4 and 5 to be two input NORs (NOR2).</span>

<span class="comment">%********************************************************************</span>
<span class="comment">% user specified data (specify problem constant and ckt topology)</span>
<span class="comment">%********************************************************************</span>
m = 7;        <span class="comment">% number of gates</span>
Vdd = 5;      <span class="comment">% supply voltage</span>
Amax = 250;   <span class="comment">% maximum area spec</span>

<span class="comment">% gate specs</span>
INV   = struct(<span class="string">'Cin'</span>,3, <span class="string">'Cint'</span>,3, <span class="string">'Rdrv'</span>,0.48, <span class="string">'A'</span>,3,  <span class="string">'Ileak'</span>,0.006);
NAND3 = struct(<span class="string">'Cin'</span>,4, <span class="string">'Cint'</span>,6, <span class="string">'Rdrv'</span>,0.48, <span class="string">'A'</span>,8,  <span class="string">'Ileak'</span>,0.007);
NOR2  = struct(<span class="string">'Cin'</span>,5, <span class="string">'Cint'</span>,6, <span class="string">'Rdrv'</span>,0.48, <span class="string">'A'</span>,10, <span class="string">'Ileak'</span>,0.009);

clear <span class="string">gates</span>;
gates([1 3 6]) = INV;
gates([2 7])   = NAND3;
gates([4 5])   = NOR2;

<span class="comment">% primary inputs and primary outputs labels (start with m+1)</span>
primary_inputs = [8 9 10];
primary_outputs = [11 12];
M = m + length( primary_inputs ) + length( primary_outputs );

<span class="comment">% fan-in cell array</span>
FI = cell(M,1);
FI{1} = [8];
FI{2} = [8 9 10];
FI{3} = [10];
FI{4} = [1 2];
FI{5} = [2 3];
FI{6} = [4];
FI{7} = [3 4 5];
FI{8} = [];
FI{9} = [];
FI{10} = [];
FI{11} = [6];
FI{12} = [7];

<span class="comment">% primary output has Cin capacitance (but has no Cload)</span>
Cin_po = sparse(M,1);
Cin_po(primary_outputs) = [10 10];

<span class="comment">% primary input has Cload capacitance (but has no Cin)</span>
Cload_pi = sparse(M,1);
Cload_pi(primary_inputs) = [10 10 10];

<span class="comment">% activity frequency of gates and primary inputs</span>
f_gates = 0.001*ones(m,1);
f_pi = sparse(M,1);
f_pi(primary_inputs) = 0.001*[10 10 10];

<span class="comment">%********************************************************************</span>
<span class="comment">% derived problem data (computed from user inputs)</span>
<span class="comment">%********************************************************************</span>
<span class="comment">% fan-out cell array (compute it from the fan-in cell array)</span>
FO = cell(M,1);
<span class="keyword">for</span> gate = [1:m primary_outputs]
  preds = FI{gate};
  <span class="keyword">for</span> k = 1:length(preds)
    FO{preds(k)}(end+1) = gate;
  <span class="keyword">end</span>
<span class="keyword">end</span>

<span class="comment">% input and internal capacitance of gates, and driving resistance</span>
Cin_norm  = [gates.Cin]';
Cint_norm = [gates.Cint]';
Rdrv_norm = [gates.Rdrv]';

<span class="comment">% area specification for each gate with unit scaling</span>
A_norm = [gates.A]';

<span class="comment">% leakage current of gate i with unit scaling</span>
Ileak_norm = [gates.Ileak]';

<span class="comment">%********************************************************************</span>
<span class="comment">% optimization (with tradeoff curve generation)</span>
<span class="comment">%********************************************************************</span>
<span class="comment">% objective is the upper bound on the overall delay</span>
<span class="comment">% and that is the max of arrival times for output gates</span>
output_gates = [FI{primary_outputs}];

<span class="comment">% varying parameters for the tradeoff curve</span>
N = 25;
Pmax = linspace(10,20,N);
min_delay = zeros(N,1);
disp(<span class="string">'Generating the optimal tradeoff curve...'</span>)
<span class="keyword">for</span> n = 1:N
  fprintf(<span class="string">'Pmax = %6.2f: '</span>,Pmax(n));
  cvx_begin <span class="string">gp</span> <span class="string">quiet</span>
    <span class="comment">% optimization variables</span>
    variable <span class="string">x(m)</span>                 <span class="comment">% scale factor</span>
    variable <span class="string">T(m)</span>                 <span class="comment">% arrival times</span>

    <span class="comment">% input capacitance is an affine function of sizes</span>
    Cin  = Cin_norm.*x;
    Cint = Cint_norm.*x;

    <span class="comment">% driving resistance is inversily proportional to sizes</span>
    R = Rdrv_norm./x;

    <span class="comment">% gate delay is the product of its driving resistance and load cap.</span>
    Cload = cvx( zeros(m,1) );
    <span class="keyword">for</span> gate = 1:m
      <span class="keyword">if</span> ~ismember( FO{gate}, primary_outputs )
        Cload(gate) = sum( Cin(FO{gate}) );
      <span class="keyword">else</span>
        Cload(gate) = Cin_po( FO{gate} );
      <span class="keyword">end</span>
    <span class="keyword">end</span>

    <span class="comment">% delay</span>
    D = 0.69*ones(m,1).*R.*( Cint + Cload );

    <span class="comment">% total area</span>
    area = A_norm'*x;

    <span class="comment">% total power calculation</span>
    Pdyn = Vdd^2*sum( f_pi(primary_inputs).*Cload_pi(primary_inputs) ) + <span class="keyword">...</span>
           Vdd^2*(f_gates'*(Cint + Cload));
    Pstat = Vdd*Ileak_norm'*x;
    power = Pdyn + Pstat;

    minimize( max( T(output_gates) ) )
    subject <span class="string">to</span>
      <span class="comment">% constraints</span>
      x &gt;= 1;
      area &lt;= Amax;
      power &lt;= Pmax(n);

      <span class="comment">% create timing constraints</span>
      <span class="keyword">for</span> gate = 1:m
        <span class="keyword">if</span> ~ismember( FI{gate}, primary_inputs )
          <span class="keyword">for</span> j = FI{gate}
            <span class="comment">% enforce T_j + D_j &lt;= T_i over all gates j that drive i</span>
            D(gate) + T(j) &lt;= T(gate);
          <span class="keyword">end</span>
        <span class="keyword">else</span>
          <span class="comment">% enforce D_i &lt;= T_i for gates i connected to primary inputs</span>
          D(gate) &lt;= T(gate);
        <span class="keyword">end</span>
      <span class="keyword">end</span>
  cvx_end
  fprintf( <span class="string">'delay = %3.2f\n'</span>, cvx_optval );
  min_delay(n) = cvx_optval;
<span class="keyword">end</span>

<span class="comment">% plot the tradeoff curve</span>
figure, clf
plot(Pmax,min_delay);
xlabel(<span class="string">'Pmax'</span>); ylabel(<span class="string">'Dmin'</span>);
title([<span class="string">'Tradeoff curve for Amax = '</span> num2str(Amax)])
disp(<span class="string">'Optimal tradeoff curve plotted.'</span>)
</pre>
<a id="output"></a>
<pre class="codeoutput">
Generating the optimal tradeoff curve...
Pmax =  10.00: delay = 14.20
Pmax =  10.42: delay = 12.33
Pmax =  10.83: delay = 11.51
Pmax =  11.25: delay = 11.02
Pmax =  11.67: delay = 10.72
Pmax =  12.08: delay = 10.48
Pmax =  12.50: delay = 10.27
Pmax =  12.92: delay = 10.08
Pmax =  13.33: delay = 9.92
Pmax =  13.75: delay = 9.78
Pmax =  14.17: delay = 9.66
Pmax =  14.58: delay = 9.54
Pmax =  15.00: delay = 9.44
Pmax =  15.42: delay = 9.35
Pmax =  15.83: delay = 9.26
Pmax =  16.25: delay = 9.18
Pmax =  16.67: delay = 9.15
Pmax =  17.08: delay = 9.15
Pmax =  17.50: delay = 9.15
Pmax =  17.92: delay = 9.15
Pmax =  18.33: delay = 9.15
Pmax =  18.75: delay = 9.15
Pmax =  19.17: delay = 9.15
Pmax =  19.58: delay = 9.15
Pmax =  20.00: delay = 9.15
Optimal tradeoff curve plotted.
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="dig_ckt_sizing__01.png" alt=""> 
</div>
</div>
</body>
</html>